package com.longge;

import java.util.ArrayDeque;
import java.util.Queue;

public class Connect {

    public Node3 connect(Node3 root) {
        if (root == null) return null;

        Queue<Node3> pq = new ArrayDeque<>();
        pq.offer(root);
        while (!pq.isEmpty()) {
            int n = pq.size();
            Node3 pre = null;
            for (int i = 0; i < n; i++) {

                Node3 node = pq.poll();
                if (node.left != null) {
                    pq.offer(node.left);
                }
                if (node.right != null) {
                    pq.offer(node.right);
                }
                if (i != 0) {
                    pre.next = node;
                }
                pre = node;
            }
        }
        return root;
    }
}
